package Graph;

import lombok.Data;
import lombok.extern.slf4j.Slf4j;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author ZAY
 * 图的工具类
 */
@Slf4j
@Data
public class Graph {
    private HashSet<Edge> graph = new LinkedHashSet<>();
    /**
     * 检查图 graph是否有以 vertex为起点的边 (货是否可以发走)
     * @param vertex 要检查的顶点
     * @return 当前点是否为起点
     */
    public boolean hasStartVertex(Vertex vertex){
        for (Edge edge : graph) {
            if(edge.getStartVertex().getVertexName().equals(vertex.getVertexName())){
                return true;
            }
        }
        return false;
    }
    /**
     * 检查图 graph是否有以 vertex为终点的边 (货是否可以送到)
     * @param vertex 要检查的顶点
     * @return 当前点是否为终点
     */
    public boolean hasEndVertex(Vertex vertex){
        for (Edge edge : graph) {
            if(edge.getEndVertex().getVertexName().equals(vertex.getVertexName())){
                return true;
            }
        }
        return false;
    }

    /**
     * 判断这个有向图存不存在环路
     * @return 是否存在环路
     */
    public boolean hasCycle(){
        Stack<Edge> stack = new Stack<>();
        for (Edge edge : graph) {
            process1(edge,stack);
        }
        return stack.isEmpty();
    }

    /**
     * 获取该图中以一个顶点为起点的所有边
     * @param vertex 指定的顶点
     * @return 以该顶点为起点的边的集合
     */
    private LinkedList<Edge> getEdge(Vertex vertex){
        LinkedList<Edge> list = new LinkedList<>();
        for (Edge edge : graph) {
            if (edge.getStartVertex().equals(vertex)) {
                list.add(edge);
            }
        }
        return list;
    }
    /**
     * 在 graph中建立单向边
     * @param edge 要建立的边
     * @return 处理后的图
     */
    public HashSet<Edge> buildSingleEdge(Edge edge){
        graph.add(edge);
        return this.graph;
    }
    /**
     * 在 graph中建立双向边
     * @param edge 要建立的边
     */
    public void buildDoubleEdge(Edge edge){
        graph.add(edge);
        graph.add(new Edge(edge.getEndVertex(),edge.getStartVertex(), edge.getLength()));
    }
    /**
     * 打印所有边
     */
    public void printGraph(){
        for (Edge edge : graph) {
            System.out.println(edge.getEdgeName());
        }
    }
    /**
     * 路径规划算法
     * @param start      起点
     * @param end        终点
     * @param isShortest 是否输出最短路径
     */
    public LinkedList<Edge> pathPlanning(Vertex start, Vertex end, boolean isShortest){
        LinkedList<Edge> list = new LinkedList<>();
        LinkedList<Edge> resultList = new LinkedList<>();
        if(!hasStartVertex(start) || !hasEndVertex(end)){
            log.error("顶点不存在");
            return resultList;
        }
        if(!isShortest){
            process(getEdge(start),end,list,resultList);
        }
        return resultList;
    }
    private void process(LinkedList<Edge> list,Vertex end,LinkedList<Edge> midList,LinkedList<Edge> resultList){
        if (list.isEmpty()){
            midList.clear();
            return;
        }
        for (Edge edge : list) {
            if (edge.getEndVertex().equals(end)){
                midList.add(edge);
                resultList.addAll(midList);
                return;
            }
            midList.add(edge);
            process(getEdge(edge.getEndVertex()),end,midList,resultList);
        }
    }
    private void process1(Edge edge, Stack<Edge> stack){
        stack.push(edge);
        for (Edge edge1 : getEdge(edge.getEndVertex())) {
            if (stack.contains(edge1)){
                stack.clear();
                return;
            }
            process1(edge1,stack);
        }
    }
}
